package LeetCode.month01.day21;

public class No808 {
    private double[][] memo;
    public double soupServings(int n) {
        //记忆化搜索 递归
        n = (int)(Math.ceil((double)n/25));
        if(n>=179) return 1;

        memo = new double[n+1][n+1];
        return dfs(n,n);

        //动态规划
//        n = (int)(Math.ceil((double)n/25));
//        if(n>=179) return 1;
//        double[][] dp = new double[n+1][n+1];
//        dp[0][0] = 0.5;
//        for (int i = 1; i <= n; i++) {
//            dp[0][i] = 1.0;
//        }
//        for (int i = 1; i <= n; i++) {
//            for (int j = 1; j <= n; j++) {
//                dp[i][j]=(dp[Math.max(0,i-4)][j]+dp[Math.max(0,i-3)][j-1]+dp[Math.max(0,i-2)][Math.max(0,j-2)]+dp[Math.max(0,i-1)][Math.max(0,j-3)])/4.0;
//            }
//        }
//        return dp[n][n];


//        double a = 0;
//        double b = 0;
//        if(n>100){
//            int[][] next = new int[][]{{-100,0},{-75,-25},{-50,-50},{-25,-75}};
//            int[][] dp = new int[n+1][n+1];
//            dp[n][n]=0;
//            for (int i = 0; i < 4; i++) {
//                dp[n+next[i][0]][n+next[i][1]]=1;
//            }
//            for (int i = n-1; i >0; i--) {
//                for (int j = n; j >0 ; j--) {
//                    if(dp[i][j]!=0){
//                        if(j>=75){
//                            if(i>=100){
//                                dp[i-100][j] += dp[i][j]+1;
//                            }
//                            if(i>=75){
//                                dp[i-75][j-25] += dp[i][j]+1;
//                            }
//                            if(i>=50){
//                                dp[i-50][j-50] += dp[i][j]+1;
//                            }
//                            if(i>=25){
//                                dp[i-25][j-75] += dp[i][j]+1;
//                            }
//                        }else if(j>=50){
//                            if(i>=100){
//                                dp[i-100][j] += dp[i][j]+1;
//                            }
//                            if(i>=75){
//                                dp[i-75][j-25] += dp[i][j]+1;
//                            }
//                            if(i>=50){
//                                dp[i-50][j-50] += dp[i][j]+1;
//                            }
//                        }else if(j>=25){
//                            if(i>=100){
//                                dp[i-100][j] += dp[i][j]+1;
//                            }
//                            if(i>=75){
//                                dp[i-75][j-25] += dp[i][j]+1;
//                            }
//                        }else{
//                            if(i>=100){
//                                dp[i-100][j] += dp[i][j]+1;
//                            }
//                        }
//                    }
//                }
//            }
//            for (int i = 0; i <= n; i++) {
//                a+=dp[i][0];
//                b+=dp[0][i];
//            }
//            return b/(a+b);
//        }else if(n>75){
//            return 0.71875;
//        }else if(n>0){
//            return 0.625;
//        }return 0.5;
    }

    private double dfs(int a, int b) {
        if (a <= 0 && b <= 0){
            return 0.5;
        }else if (a <= 0) {
            return 1;
        } else if (b <= 0) {
            return 0;
        }
        if (memo[a][b] == 0) {
            memo[a][b] = 0.25 * (dfs(a - 4, b) + dfs(a - 3, b - 1) + dfs(a - 2, b - 2) + dfs(a - 1, b - 3));
        }
        return memo[a][b];
    }
}
/*     (1+1+0.625)*0.25  2.625 0.65625
    75  75
    25  25
    1+0.5+0.5+0.5 2.5*0.25



    100     100
    1+0.25*(2) +0.25*(3)+0.25*(4)  (1+7.5*0.25)*0.25
    25      75                      1+1.875 2.875 0.71875
    1+1+1+0.5=3.5
    50      50
    1+1+0.5
    75      25
    1+0.5



    25 25
    1 0.5 0.5 0.5 2.5
 */